\chapter{Лекция 8. Контекстно-свободные языки и магазинные автоматы}

\section{Недетерминированный магазинный автомат}

\begin{Def}
Недетерминированный магазинный автомат (НМА) состоит из следующих объектов:

$X$ - входной алфавит

$Q$ - алфавит состояний

$\Gamma$ - алфавит магазинных символов

$\gamma_0 \in \Gamma$ - начальный символ магазина

$q_0 \in Q$ - начальное состояние автомата

$R$ - набор правил переходов между состояниями. Каждое правило перехода имеет вид:

$$q, a, \gamma \rightarrow p,w$$
где $q$ - состояние автомата, $a$ - входной символ (возможно $\varepsilon$), $\gamma$ - вершина магазина (стека) автомата, $p$ - состояние, в которое переходит автомат, $w$ - цепочка
магазинных символов (возможно пустая), которая ложится на верх магазина автомата вместо $\gamma$.

Цепочка допускаяется автоматом, если распознование такой цепочки съедает весь магазин автомата, кроме
самого маркера дна, т. е. в конце работы его магазин будет содержать только маркер дна магазина
и вся цепочка будет прочитана.
\end{Def}

\paragraph{Пример:} язык правильных скобочных последовательностей.

$Q = \lbrace q_0, err \rbrace$

$X = \lbrace (, )\rbrace$

$\Gamma = \lbrace \gamma_0, ( \rbrace$

Правила будут следующими:

$q_0, ), \gamma_0 \rightarrow err, \gamma_0$

$q_0, (, \gamma_0 \rightarrow q_0, \gamma_0 ($

$q_0, ), ( \rightarrow q_0, \varepsilon$

$q_0, (, ( \rightarrow q_0, ( ($

$q_0, \varepsilon, ( \rightarrow err, ( ($

\section{Детерминированный магазинный автомат}

Аналогичен НМА, с той лишь разницей, что для каждой тройки $q, a, \gamma$ существует не более одного
правила перехода и нет тройки $q, \varepsilon, \gamma$.

В отличие от пары КА и НКА, ДМА и НМА разбирают несколько разные языки, точнее ДМА разбирает строго меньше языков, ярким примером может служить язык палиндромов, где предсказание середины слова -
чистой воды преждсказание.

По грамматике можно построить НМА без особых проблем, а вот обратное утверждение уже не так очевидно,
но все еще справделиво, докажем это.

Пусть имеется НМА, построим по нему грамматику. Каждой тройке $pAq$, где $p,q \in Q$ и $A \in \Gamma$,
сопостаим нетерминал грамматики, кроме того введем отдельный начальный нетерминал $S$. Первые правила
перехода будут выглядеть так: $S ::= [q_0 \gamma_0 p]$, где $p \in Q$. Далее для каждого правила
автомата вида $q, a, A \rightarrow q_1, B_1 .... B_m$ ,где $A, B_i \in \Gamma$, $q, q_1 \in Q$ и
$a \in X$ добавим правило $[qAp] ::= a[q_1 B_1 p_1][p_1 B_2 p_2][p_2 B_3 p_3]...[p_m B_m p]$, где $p, p_i$ принимают все возможные варианты из множества состояний автомата ($p,p_i \in Q$)

Кроме того для $\varepsilon$ переходов вида $q,A \rightarrow q_1, B_1 .... B_m$ добавляем правила вида: $[qAp] ::= [q_1 B_1 p_1][p_1 B_2 p_2][p_2 B_3 p_3]...[p_m B_m p]$

Логика примерно такая: $[qAp]$ -соответсвует состоянию $q$ автомата с вершиной магазина $A$, а $p$
означет, что мы пытаемся съесть некоторую строку из состояния $q$ перейти в состояние $p$, поэтому
и $a[q_1 B_1 p_1][p_1 B_2 p_2][p_2 B_3 p_3]...[p_m B_m p]$ как раз описывает ту цепочку, которую
нужно съесть, чтобы перейти в $p$.

